1. Field of the Invention
The present invention relates to a Viterbi decoder, and more particularly, to an apparatus configuration for supplying and storing a state metric used during add-compare-select (ACS) operations in a Viterbi decoder that uses a number of ACS units to enhance decoding speed.
2. Description of the Related Art
A Viterbi decoder is an apparatus that decodes codewords, encoded by a convolutional code, by using a maximum likelihood method. The Viterbi decoder compares an encoding state of a predetermined encoder with that of a received codeword, selects the closest encoding path, and decodes information transmitted from the selected path.
FIG. 1 is a block diagram showing a conventional Viterbi decoder. The Viterbi decoder shown in FIG. 1 includes a branch metric calculator 10, an ACS unit 12, a state metric memory 14, a path memory 16, and a path tracing logic unit 18.
When the apparatus shown in FIG. 1 receives a codeword, the branch metric calculator 10 calculates the similarity (Hamming distance) between the received codeword and a predetermined codeword, which can be output from an encoder (not shown), and outputs a branch metric BM. The ACS unit 12 receives the branch metric BM provided from the branch metric calculator 10 and a previous (old) state metric OSM stored in the state metric memory 14 as inputs, and performs an add-compare operation to select a survival path showing an encoding sequence closest to that of the received codeword and calculate a current (new) state metric NSM of the survival path. The selected survival path is stored in the path memory 16 and the calculated current state metric NSM is stored in the state metric memory 14. The path tracing logic unit 18 refers to the survival path memory in the path memory 16 and outputs decoded data based on an encoding path of the received codeword.
The number of states N which can exist for a single codeword, among the received codewords in Viterbi decoding, is defined as 2.sup.K-1, where K is defined as a constraint length. When the ACS unit 12 of FIG. 1, which calculates the state metric of the survival path, has N number of states, the apparatus shown in FIG. 1 maintains the fastest processing speed. This is because N ACS units each simultaneously perform an ACS operation, with respect to the N states which can exist in correspondence to a single codeword.
Therefore, with respect to decoding speed, it is preferable that N ACS units be used for codeword having N states. However, it is difficult to make a large capacity ACS unit. Thus, as the state number N becomes larger, the number of ACS units must be selected appropriately.
A convolutional code having a constraint length K of 9 is used in a general code division multiple access (CDMA) system, therefore, the state number becomes 256 (2.sup.a-1). If a Viterbi decoder uses 256 ACS units, decoding speed is fast, but more hardware is required. However, when a single ACS unit is used in a Viterbi decoder, less hardware is required, but decoding speed is slow.
A Viterbi decoder using a single ACS unit is disclosed in Korean patent application No. 90-20808 filed on Dec. 17, 1990, by the same applicants, entitled "State metric storage device". This device can perform fast input and output processing of a state metric when a single ACS unit is used, but cannot be used when a number of ACS units are used.
A technology for enhancing decoding speed using a number of ACS units is disclosed in Korean patent application No. 96-7208 filed on Mar. 18, 1996, by the same applicants, entitled "ACS device of Viterbi decoder". This device uses four ACS units to enhance decoding speed. However, since the device includes a typical state metric memory, that is comprised of a single memory device, the input and output speed of the state metric are somewhat slow.
A technology for solving the above problems is disclosed in Korean patent application No. 97-8603, filed on Mar. 14, 1997, by the same applicants, entitled "State metric storing method and apparatus for Viterbi decoder". This apparatus uses two-state metric storing units that are comprised of two memory devices, to efficiently supply and store the state metric used during add-compare-select operations. However, since a memory capacity of 2N is required, where N is the number of states, the memory capacity of the state metric storing unit becomes larger as N increases, which is burdensome.